class Solution {
    public int numSquares(int n) {
        int[] db = new int[n + 1];
        return digui(n, db);

    }

    public int digui(int n, int[] db) {
        int count = Integer.MAX_VALUE;
        if (db[n] != 0) {
            return db[n];
        }
        if (n == 0) {
            return 0;
        }
        for (int i = 1; i * i <= n; i++) {
            count = Math.min(count, digui(n - i * i, db) + 1);
        }
        db[n] = count;
        return count;
    }
}